package leetcode_day._2021._202105._2131;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/5/26 21:44
 * 反转每对括号间的子串
 * 算法：栈
 * 如果栈中没有元素，就直接添加在 ans 后面
 * 如果有，则放入栈中
 * 碰到 '(' 就入栈，')' 则出栈，再入栈
 */
public class _26_1190 {

    public String reverseParentheses(String s) {
        StringBuilder ans = new StringBuilder();
        Deque<Character> stack = new ArrayDeque<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            char c = chars[i];
            if (c == '(') stack.push(c);
            if (c >= 'a' && c <= 'z') {
                if (stack.isEmpty()) ans.append(c);
                else stack.push(c);
            }
            if (c == ')') {
                String res = reverse(stack);
                if (!"-1".equals(res)) ans.append(res);
            }
        }
        return ans.toString();
    }
    public String reverse(Deque<Character> stack) {
        String res = "-1";
        StringBuilder tmp = new StringBuilder();
        while (!stack.isEmpty() && stack.peek() != '(') tmp.append(stack.pop());
        stack.pop();
        if (stack.isEmpty()) res = tmp.reverse().toString();
        for (char c : tmp.toString().toCharArray()) stack.push(c);
        return res;
    }

    // 碰到 '(' 就把 ans 存入到栈中，如果是 ')' 就拿出来
    public String reverseParentheses_perfect(String s) {
        Deque<String> stack = new LinkedList<>();
        StringBuilder ans = new StringBuilder();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(ans.toString());
                ans.setLength(0);
            } else if (c == ')') {
                ans.reverse();
                ans.insert(0, stack.pop());
            } else ans.append(c);
        }
        return ans.toString();
    }

}
